Implement Rand10() Using Rand7()

Leetcode #470 | Medium | Математика | Design

Идея

Идея перевести рандомом в матрицу 7 на 7, где 49 чисел. Вероятность у них одинаковая. Если выпало >40 то рероллим. У нас остались от 1 до 40. Переводим их в 1..10. -1 тут нужны чтобы переводить в 1.. а не в 0..
Док-во перевода: P(число в матрице|попали в диапазон 40) = 1/49 : 40/49 = 1/40 - то есть все равновероятно, ну а каждая цифра от 1 до 10 потом имеет тоже одинаковую вероятность
Пояснение для формулы условной вероятности: любое число 1..7 входит в диапазон 1..40 поэтому P(A\intersectB) = 1/49, ну а P(B)=40/49

Big-O

• Время O(1)
• Память O(1)

Код

class Solution extends SolBase {
    public int rand10() {
        int num = 41;
        while (num > 40) num = (rand7() - 1) * 7 + rand7();
        return (num - 1) % 10 + 1;
    }
}